package 力扣._42_接雨水;

import java.util.Stack;

public class Solution2 {
    public int trap(int[] height) {
        //先找到每一个节点的左边最大和右边最大值的下标
        if(height.length<3)
            return 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        max_left[1] = 0;
        for (int i = 2; i < height.length; i++) { //下标i，i-1之间的最大元素
            if (height[max_left[i - 1]] < height[i - 1]) {
                max_left[i] = i - 1;
            } else
                max_left[i] = max_left[i - 1];
        }
        max_right[height.length - 2] = height.length - 1;
        for (int i = height.length - 3; i >= 0; i--) {
            if (height[max_right[i + 1]] < height[i + 1]) {
                max_right[i] = i + 1;
            } else {
                max_right[i] = max_right[i + 1];
            }
        }
        int sum = 0;
        //当前位置的雨水等于左右最低高度减去当前位置高度
        for (int i = 1; i < height.length - 1; i++) {
            int h = Math.min(height[max_left[i]], height[max_right[i]]);
            sum += Math.max(h - height[i], 0);
        }
        return sum;

    }

    public static void main(String[] args) {
        int[] h = new int[]{0};
        int trap = new Solution2().trap(h);
        System.out.println(trap);
    }
}
